package nk.dp;

import java.util.Scanner;

public class AB41 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int V = scanner.nextInt();

        int[] vol = new int[n + 1];
        int[] wei = new int[n + 1];

        int[][] dp1 = new int[n + 1][V + 1];
        int[][] dp2 = new int[n + 1][V + 1];


        for (int i = 1; i <= n; i++) {
            vol[i] = scanner.nextInt();
            wei[i] = scanner.nextInt();
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                if (j < vol[i]) {
                    dp1[i][j] = dp1[i-1][j];
                } else { //dp1[i][j - vol[i]] + wei[i] 与01背包的差别，01背包是dp1[i - 1][j - vol[i]] + wei[i]
                    dp1[i][j] = Math.max(dp1[i-1][j], dp1[i][j - vol[i]] + wei[i]); //
                }
            }
        }

        System.out.println(dp1[n][V]);

        for (int i = 0; i <= n ; i++) {
            for (int j = 1; j <= V ; j++) {
                dp2[i][j] = Integer.MIN_VALUE;
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V ; j++) {
                if (j < vol[i]) {
                    dp2[i][j] = dp2[i-1][j];
                } else {
                    dp2[i][j] = Math.max(dp2[i-1][j], dp2[i][j - vol[i]] + wei[i]);
                }
            }
        }
        System.out.println(dp2[n][V] < 0 ? 0 : dp2[n][V]);
    }



}
